package leetcode;

import java.util.*;

public class Code20 {
    public static void main(String[] args) {
        List<Map.Entry<Integer, Double>> aaa = new Code20().dicesSum2(10);
        for (Map.Entry<Integer, Double> a : aaa) {
            System.out.println(" " + a.getKey() + ":" + a.getValue());
        }
    }

    /**
     * 使用hashmap
     *
     * @param n
     * @return
     */
    public List<Map.Entry<Integer, Double>> dicesSum(int n) {
        HashMap<Integer, Double> sum = new HashMap<>();
        for (int a = 1; a <= n; a++) {
            for (int b = a * 6; b >= a; b--) {
                int start = 0;
                int end = 0;
                if (b > (a - 1) * 6) {
                    start = b - 6;
                    end = (a - 1) * 6;
                } else {
                    end = b - 1;
                    start = b - 6 < a ? a - 1 : b - 6;
                }
                double all = 0;
                while (a != 1 && start <= end) {
                    all += sum.get(start);
                    start++;
                }
                if (all == 0) {
                    all = 1;
                }
                sum.put(b, all);
            }
        }
        ArrayList<Map.Entry<Integer, Double>> needlist = new ArrayList<>();
        for (int a = n; a <= 6 * n; a++) {
            AbstractMap.SimpleEntry<Integer, Double> entry = new AbstractMap.SimpleEntry<Integer, Double>(a, sum.get(a) / Math.pow(6, n));
            needlist.add(entry);
        }
        return needlist;
    }

    public List<Map.Entry<Integer, Double>> dicesSum2(int n) {
        double[] dp = new double[n * 6 + 1];
        dp[0] = 1;
        for (int a = 1; a <= n; a++) {
            for (int b = a * 6; b >= a; b--) {
                int start = 1;
                start = b - 6 >= a-1 ? b - 6 : a-1;
                int end = start+5>(a-1)*6?(a-1)*6:start+5>=b?b-1:start+5;
                double all = 0;
                while (start <= end) {
                    all += dp[start];
                    start++;
                }
                if (a != 1) {
                    dp[b] = all;
                } else {
                    dp[b] = 1;
                }
            }
        }
        ArrayList<Map.Entry<Integer, Double>> needlist = new ArrayList<>();
        double all= Math.pow(6, n);
        for (int a = n; a <= 6 * n; a++) {
            AbstractMap.SimpleEntry<Integer, Double> entry = new AbstractMap.SimpleEntry<Integer, Double>(a, dp[a] /all);
            needlist.add(entry);
        }
        return needlist;
    }
}
